If the postorder and inorder traversal sequences of a binary tree are the same, then none of the nodes in the tree has a right child. (2分)

$N(logN)^2$ is $O(N^2)$. (2分)

If the most commonly used operations are to visit a random position and to insert and delete the last element in a linear list, then sequential storage works the fastest. (2分)

Given the input sequence onto a stack as {1, 2, 3, ..., $N$}. If the first output is $i$, then the $j$-th output must be $j-i-1$. (2分)

The best "worst-case time complexity" for any algorithm that sorts by comparisons only must be $O(NlogN)$. (2分)

For a binary search tree, in which order of traversal that we can obtain a non-decreasing sequence? (3分)

1. preorder traversal
2. postorder traversal
3. inorder traversal
4. level-order traversal

Which one of the following relations is correct about the extra space taken by heap sort, quick sort and merge sort? (3分)

1. heap sort $<$ merge sort $<$ quick sort
2. heap sort $>$ merge sort $>$ quick sort
3. heap sort $<$ quick sort $<$ merge sort
4. heap sort $>$ quick sort $>$ merge sort

Given the pushing sequence of a stack as {1, 2, 3, 4, 5}. If the first number being popped out is 4, then the last one out must be: (3分)

1. 1
2. 3
3. 5
4. 1 or 5

Insert {5, 2, 7, 3, 4, 1, 6} one by one into an initially empty min-heap. The preorder traversal sequence of the resulting tree is: (6分)

1. 1, 3, 2, 5, 4, 7, 6
2. 1, 2, 3, 4, 5, 7, 6
3. 1, 2, 5, 3, 4, 7, 6
4. 1, 3, 5, 4, 2, 7, 6

Given a tree of degree 4. Suppose that the numbers of nodes of degrees 2, 3 and 4 are 4, 2 and 1, respectively. Then the number of leaf nodes must be: (6分)

1. 8
2. 12
3. 18
4. 20

Suppose that the height of a binary tree is $h$ (the height of a leaf node is defined to be 1), and it has only the nodes of degrees 0 and 2. Then the minimum and maximum possible total numbers of nodes are: (6分)

1. $2h$, $2^h-1$
2. $2h-1$, $2^h-1$
3. $2h-1$, $2^{h-1}-1$
4. $2^{h-1}+1$, $2^h-1$

Suppose that an array of size m is used to store a circular queue. If the front position is front and the current size is size, then the rear element must be at: (6分)

1. front+size
2. front+size-1
3. (front+size)%m
4. (front+size-1)%m

Suppose that the level-order traversal sequence of a min-heap is {1, 3, 2, 5, 4, 7, 6}. Use the linear algorithm to adjust this min-heap into a max-heap. The inorder traversal sequence of the resulting tree is: (6分)

1. 3, 5, 4, 2, 6, 1, 7
2. 1, 4, 3, 7, 2, 6, 5
3. 3, 5, 4, 7, 2, 6, 1
4. 4, 1, 3, 7, 6, 2, 5

Among the following sorting methods, which one may cause that none of the elements are at their final positions before the last run begins? Assume that there are more than 2 elements to be sorted. (3分)

1. bubble sort
2. insertion sort
3. heap sort
4. quick sort

To delete p from a doubly linked list, we must do: (6分)

1. p->prior=p->prior->prior; p->prior->next=p;
2. p->next->prior=p; p->next=p->next->next;
3. p->prior->next=p->next; p->next->prior=p->prior;
4. p->next=p->prior->prior; p->prior=p->next->next;

Given input { 321, 156, 57, 46, 28, 7, 331, 33, 34, 63 }. Which one of the following is the result after the 1st run of the Least Signification Digit (LSD) radix sort? (4分)

1. →331→321→33→63→34→156→46→57→7→28
2. →321→331→33→63→34→156→46→57→7→28
3. →156→28→321→331→33→34→46→57→63→7
4. →57→46→28→7→33→34→63→156→321→331

The array representation of a disjoint set containing numbers 0 to 8 is given by { 1, -4, 1, 1, -3, 4, 4, 8, -2 }. Then to union the two sets which contain 6 and 8 (with union-by-size), the index of the resulting root and the value stored at the root are: (6分)

1. 1 and -6
2. 4 and -5
3. 8 and -5
4. 8 and -6

If on the 9th level of a complete binary tree (assume that the root is on the 1st level) there are 100 leaf nodes, then the maximum number of nodes of this tree must be: (6分)

1. 311
2. 823
3. 1847
4. cannot be determined

The function is to lower the value of the integer key at position P by a positive amount D in a min-heap H.

void DecreaseKey( int P, int D, PriorityQueue H )
{
   int i, key;
   key = H->Elements[P] - D;
   for ( i = (3分); H->Elements[i/2] > key; i/=2 )
      (3分);
   H->Elements[i] = key;
}